/*
 * @lc app=leetcode.cn id=1475 lang=cpp
 *
 * [1475] 商品折扣后的最终价格
 */

// @lc code=start
class Solution {
public:
    vector<int> finalPrices(vector<int> &prices) {
        int n = prices.size();
        vector<int> ans(n);
        stack<int> stk;
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && stk.top() > prices[i]) {
                stk.pop();
            }
            ans[i] = stk.empty() ? prices[i] : prices[i] - stk.top();
            stk.emplace(prices[i]);
        }

        return ans;
    }
};
// @lc code=end
